package dmsxl.haxibiao;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/14 20:13
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 */
public class hxb2_r3_438 {

    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        System.out.println(findAnagrams(s, p));
    }

//    自己写的，效果很差
    public static List<Integer> findAnagrams1(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] pl = new int[26];
        for (int i = 0; i < p.length(); i++) pl[p.charAt(i)-'a']++;
        for (int i = 0; i <= s.length()-p.length(); i++){
            int[] tem = Arrays.copyOf(pl, 26);
            for (int j = i; j < i + p.length(); j++){
                tem[s.charAt(j)-'a']--;
            }
            System.out.println(Arrays.toString(tem));
            int count = 0;
            for (int k = 0; k < 26; k ++){
                if (tem[k]==0) count++;
            }
            if (count==26) res.add(i);
        }
        return res;
    }

//    看的题解，滑动窗口
    public static List<Integer> findAnagrams2(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;
        int[] pl = new int[26];
        int[] sl = new int[26];
        for (int i = 0; i < p.length(); i++){
            pl[p.charAt(i)-'a']++;
            sl[s.charAt(i)-'a']++;
        }
        if (Arrays.equals(sl,pl))
            res.add(0);
        for (int i = 0; i < s.length() - p.length(); i++){
            sl[s.charAt(i)-'a']--;
            sl[s.charAt(i+p.length())-'a']++;
            if (Arrays.equals(sl, pl))
                res.add(i+1);
        }
        return res;
    }

//    在题解1的基础上优化(效果相差不大)
    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }
        System.out.println(Arrays.toString(count));
        int differ = 0;
        for (int j = 0; j < 26; j++) {
            if (count[j] != 0) {
                differ++;
            }
        }
        if (differ == 0) {
            ans.add(0);
        }
        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];

            if (differ == 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}
